{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 归并排序"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 -> 2 -> 1 -> 3 -> None\n",
      "1 -> 2 -> 3 -> 4 -> None\n"
     ]
    }
   ],
   "source": [
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "class Solution:\n",
    "    def sortList(self, head: ListNode) -> ListNode:\n",
    "\n",
    "        def merge(list1, list2):\n",
    "            dummy = cur = ListNode()\n",
    "            while list1 and list2:\n",
    "                if list1.val <= list2.val:\n",
    "                    cur.next = list1\n",
    "                    list1 = list1.next\n",
    "                else:\n",
    "                    cur.next = list2\n",
    "                    list2 = list2.next\n",
    "                cur = cur.next\n",
    "            cur.next = list1 if list1 else list2\n",
    "            return dummy.next\n",
    "        \n",
    "        def sortf(h, t):\n",
    "            # 0 个结点\n",
    "            if not h:\n",
    "                return h\n",
    "            # 1 个节点，左开右闭区间\n",
    "            if h.next == t:\n",
    "                h.next = None\n",
    "                return h\n",
    "            # 快慢指针找到 mid\n",
    "            slow = fast = h\n",
    "            while fast != t:\n",
    "                slow = slow.next\n",
    "                fast = fast.next\n",
    "                if fast != t:\n",
    "                    fast = fast.next\n",
    "            return merge(sortf(h, slow), sortf(slow, t))\n",
    "        \n",
    "        return sortf(head, None)\n",
    "\n",
    "\n",
    "# Function to print the sorted linked list\n",
    "def printList(head):\n",
    "    while head:\n",
    "        print(head.val, end=\" -> \")\n",
    "        head = head.next\n",
    "    print(\"None\")\n",
    "\n",
    "# Define the list nodes\n",
    "d = ListNode(3)\n",
    "c = ListNode(1, d)\n",
    "b = ListNode(2, c)\n",
    "a = ListNode(4, b)\n",
    "\n",
    "# Create an instance of Solution\n",
    "solution = Solution()\n",
    "\n",
    "# Print the linked list\n",
    "printList(a)\n",
    "\n",
    "# Print the sorted linked list\n",
    "printList(solution.sortList(a))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
